Leetcode 581.最短无序连续子数组

题目描述：

给你一个整数数组 nums ，你需要找出一个 连续子数组 ，如果对这个子数组进行升序排序，那么整个数组都会变为升序排序。

请你找出符合题意的 最短 子数组，并输出它的长度。

进阶：你可以设计一个时间复杂度为 O(n) 的解决方案吗？

示例 1：

1
2
3

输入：nums = [2,6,4,8,10,9,15]
输出：5
解释：你只需要对 [6, 4, 8, 10, 9] 进行升序排序，那么整个表都会变为升序排序。

示例 2：

1
2

输入：nums = [1,2,3,4]
输出：0

示例 3：

1
2

输入：nums = [1]
输出：0

提示：

• $1 <= nums.length <= 10^4$
• $-10^5 <= nums[i] <= 10^5$

链接：

https://leetcode-cn.com/problems/shortest-unsorted-continuous-subarray

题目分析

  这个子数组将原数组分成了三段，左边和右边都是排好序的数组，并且要满足这三段中的任意数都有大小关系。也就是说中间的任一个数都比左边的大。进阶要求提示我们应该使用遍历就可以完成，如何在遍历中找到分割数组的端点呢？
  我们先考虑左边，如果是按照从右到左的遍历顺序维护一个最小值，那么在左边的数组中，应该可以不断更新最小值，而最后一个不满足这样性质的就是左端点。我们使用一个例子来辅助理解。比如我们有这样一个数组 [1,2,3,5,6,4,9,7,8,10,11,12]，分割的区间应该是 [5 ~ 8]。先观察一下左端点 5 的性质，它其实仍然是大于 3 的，但是它比 4 大，所以已经属于中间的数组了，我们从右向左遍历，遍历到 4 的时候就记录到了最小值 4，而遍历到 5 的时候可以将左端点记录为 5（因为它比 4 大），而继续遍历 3、2、1 的时候则是不断更新最小值，那么更新最小值的时候就可以不用更新左端点。
  上面的分析中，从右到左遍历可以获得左端点，那同理从左到右遍历应该可以获得右端点。并且获得左端点是维护最小值，获得右端点是维护最大值，这两个过程是不冲突的，可以同时进行的，那么我们只使用一趟遍历就可以了。
  最后再考虑一下边界情况。如果数组最开始就是有序的，那么我们应该找不到左右端点，这个时候左右端点就是初始值，而返回结果应该是 0。另一种是数组中也可能出现同数字，这个时候要更新最值还是更新端点呢？我们考虑 [1,3,2,4,4] 这样的数组，它的分割区间应该是 [3,2]，从左到右遍历时，遍历到第二个 4 的时候，它与当前最大值相同，这个时候右端点不应该更新，而它与最大值相同，更新最大值是不会产生任何影响的。所以我们应该将等于最值的情况归为更新最值的办法中。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution {
public:
    int findUnsortedSubarray(vector<int>& nums) {
        int n = nums.size();
        int left = -1, right = -1;
        int minn = INT_MAX, maxn = INT_MIN;
        for(int i = 0; i < n; i++){
            if(nums[i] >= maxn){
                maxn = nums[i];
            }
            else{
                right = i;
            }
            if(nums[n - i - 1] <= minn){
                minn = nums[n - i - 1];
            }
            else{
                left = n - i - 1;
            }
        }
        return left == right ? 0 : right - left + 1;
    }
};

  时间复杂度：$O(n)$，其中 $n$ 是数组的大小。我们只需要对数组进行一次遍历。
  空间复杂度：$O(1)$。我们只需要常数个变量的空间。